3.9 KB · ⇊ 2 parts · ⤓ Micron 3.9 KB · ⤓ HTML 23.0 KB

top

Speedup (englisch für Beschleunigung) ist ein Begriff aus der Informatik und beschreibt mathematisch den Zusammenhang zwischen der seriellen und der parallelen Ausführungszeit eines Programmteils.

• Definition

• Wertebereich

• Siehe auch

• Literatur

• Einzelnachweise

Der Speedup S p {\displaystyle S_{p}} einer parallelen Ausführung kann anhand der Gleichung

S p = T 1 T p {\displaystyle S_{p}={\frac {T_{1}}{T_{p}}}}

definiert werden. Dabei stellen T 1 {\displaystyle T_{1}} und T p {\displaystyle T_{p}} die serielle sowie parallele Ausführungszeit dar. Die obige Gleichung wird für eine Messung des realen Speedups herangezogen. Wird der theoretische Wert betrachtet, so kann dieser mittels dem Ausdruck

S p = T 1 T 1 ( ( 1 − − f ) + f p ) {\displaystyle S_{p}={\frac {T_{1}}{T_{1}\left(\left(1-f\right)+{\frac {f}{p}}\right)}}}

dargestellt werden. Dabei gilt:

• p {\displaystyle p} ist die Anzahl von Prozessoren

• S p {\displaystyle S_{p}} ist der theoretische Speedup, der erreicht werden kann bei Ausführung des Algorithmus auf p {\displaystyle p} Prozessoren

• T 1 {\displaystyle T_{1}} ist die Ausführungszeit auf einem Ein-Prozessor-System

• T p {\displaystyle T_{p}} ist die Ausführungszeit auf einem Mehrprozessorsystem

• f {\displaystyle f} (engl. fraction) ist der Anteil von T 1 {\displaystyle T_{1}} , welcher parallel ausgeführt werden kann

Im Idealfall gilt

S p = p {\displaystyle S_{p}=p}

sodass die Ausführungszeit auf p {\displaystyle p} Prozessoren genau p {\displaystyle p} -mal so schnell ist, als auf nur einem Prozessor. Da jedoch ein Algorithmus nie komplett zu 100 % parallel ausgeführt werden kann, weil es immer einen sequenziellen nicht parallelisierbaren Anteil gibt, ist der Idealfall nie erreichbar (siehe Amdahlsches Gesetz).

Der Wertebereich lässt sich daher festlegen mit

1 ≤ ≤ S p ≤ ≤ p {\displaystyle 1\leq S_{p}\leq p}

wobei der Speedup nur dann 1 ist, falls der komplette Algorithmus nicht parallelisierbar ist und daher auf mehreren Prozessoren genauso schnell abgearbeitet wird, wie auf nur einem Prozessor.

• Amdahlsches Gesetz

• Parallelrechner

• Speedup beim Pipelining

• Speedup-Theorem in der Komplexitätstheorie

• Speedup messen und visualisierencite-ref-1[1]

• Rahm, Erhard. Mehrrechner-Datenbanksysteme - Grundlagen der verteilten und parallelen Datenbankverarbeitung (Speedup und Scaleup). Leipzig: 1994.

cite-note-11. ↑ Speedup messen und visualisieren